/*
 * @lc app=leetcode.cn id=440 lang=javascript
 *
 * [440] 字典序的第K小数字
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
function getCount(prefix, n) {
  let count  = 0;
  for (let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10) {
    count += Math.min(next, n + 1) - cur;
  }
  return count;
}

var findKthNumber = function(n, k) {
  // 指向当前位置，当cur === k时，就是排位第k的数
  let cur = 1;

  let prefix = 1; // 前缀
  while(cur < k) {
    let count = getCount(prefix, n); // 当前前缀的所有子节点的数量
    if(cur + count > k) { //第k个数在当前前缀下
      prefix *= 10;
      cur++;
    } else {
      prefix++;
      cur += count;
    }
  }

  return prefix;
};

// @lc code=end

